This application is based on an application No. 11-137762 filed in Japan, the content of which is hereby incorporated by reference.
1. Field of the Invention
The invention relates to a program conversion technique, and in particular to a technique that uses a compiler to assist in the management of dynamic memory allocation by the execution thread.
2. Related Art
Most conventional programming languages use several types of variables. These may be classified into global variables, which are allocated memory throughout execution of an entire program, local variables, which are allocated memory only when a local section of a program, such as inside a particular function, is executed, and dynamic variables, which are allocated memory dynamically using a code within a program. Examples of codes for allocating memory dynamically to variables are the library function malloc used in C programming language and the object generating operator new used in Java(trademark).
Memory allocated to a local variable is certain to be freed once execution of a local program section, such as calling a function, has been completed, but it is more difficult to determine the point in the program at which a dynamic variable will no longer be required. The following is an explanation of the use of dynamic variables.
When dynamic variables are used by a computer, the size of an area used for dynamic memory allocation of variables (the heap area) is limited. This means that some kind of mechanism is required to free the part of the heap area allocated to variables that are no longer in use, thereby allowing it to be used by new variables.
The methods used to free the part of the heap area occupied by data (variables) that are no longer in use, can be roughly divided into two, depending on which type of programming language is used.
1. The programmer explicitly writes an instruction for freeing memory in the source program, in the same way as when memory is allocated. This method forms part of what is known as manual memory management.
2. A program execution thread determines whether data allocated memory in the heap area is still in use or not, and frees memory allocated to data that is no longer in use. This method forms part of what is known as automatic memory management.
FIG. 1 illustrates the generation of execution-format code in C, C++ and Java.
As shown in FIG. 1A, programming languages such as C and C++ use a manual memory management method ((1) above), in which a source program is converted into machine code by a compiler (linker) and the machine code is executed directly as execution format code. In C, memory is allocated by the library function malloc and freed by a library function free, while in C++ memory is allocated by an operator new and freed by an operator delete.
Programming languages such as Java, however, use automatic memory management ((2) above), as shown in FIG. 1B. Here, a source program is first converted into Java bytecode by the compiler (linker). Then an interpreter translates the Java bytecode into execution-format code and executes it. In Java, memory is allocated by the object generating operator new and freed by the interpreter.
The following is a more detailed explanation of the way that memory is freed in these memory management methods.
In manual memory management, memory is freed by an explicit program instruction, so that responsibility for freeing memory rests with the program, and the execution thread does not determine whether data in the heap area is in use or not.
However, in a program written in C++ or similar, a free instruction may be erroneously omitted from the program by the programmer, thereby preventing the recycling of memory which is no longer in use and should therefore be freed. As a result, the amount of available memory may be insufficient to execute the program, and the original program will have difficulty in specifying the cause of such lack of memory. Conversely, suppose that memory which is still being used by the program is freed by mistake (also known as a premature free). If the data that was allocated to this memory is required again by the program, the resulting program bug is extremely difficult to trace.
Having the program indicate appropriate times for freeing memory when using a manual memory management method such as (1) is on occasion an extremely difficult task. The resulting discrepancy between memory holding data that is no longer in use and memory that is actually freed by the program means that there is always a risk of generating the above-described inefficiencies.
In the automatic memory management method (2), however, only the allocation of memory is indicated in the program, and the freeing of memory is left wholly to the execution thread (through the automatic memory management of the interpreter). This avoids the risks posed by the manual memory management method (1), thereby allowing the proper use of data which has been dynamically allocated memory.
In a Java interpreter (execution thread) used in the automatic memory management method (2), dynamic memory management can be smoothly performed using garbage collection. Garbage collection consists of xe2x80x98identificationxe2x80x99 processing for determining whether data stored in the heap area is in use (alive), or not in use (garbage), and xe2x80x98recyclingxe2x80x99 processing for collecting into one all memory allocated to data which has been determined to be no longer in use.
Object-orientated languages have become a focus of attention in recent years for reasons such as their high degree of program re-use. Most object-orientated languages allocate memory in the heap area to objects, so that the execution capability of an application written in object-orientated language is frequently determined by the success rate of memory management performed by execution threads.
Both C++ and Java are object-orientated languages, but since Java uses automatic memory management, freeing dynamically-generated objects is left entirely to a garbage collector (the device performing garbage collection).
The following is one example of a program written in Java.
for (i=0;i less than 1000;i++){
g.setcolor(new color(0,0,i))// set a color for object g
g.line(0,1,999,i) } // draw a line under object g
In this program, the operator new is used in a for loop to dynamically generate an object in a class color. However, a color class object is only used for a short period due to the fact that a different color is set on each loop repetition, so that the color class object is likely to become garbage immediately following the execution of g.setcolor(new color (0,0,i)) for each value of i.
An instruction set for a Java virtual machine (a bytecode execution thread including an interpreter) conforming to the specifications stipulated by Sun Microsystems Inc does not include an instruction for freeing heap area. In other words, freeing of memory in the part of the heap area that is allocated to objects is performed entirely by the garbage collector in Java, so that the garbage collector is responsible for deleting all of the 1000 objects generated inside the for loop in the above program.
However, it is generally well-known that execution of garbage collection by the garbage collector expends a great deal of time (processing cost). According to page 45 of the July 1998 issue of the monthly magazine Java World, published by IDG Communications, roughly 20% of the execution time in a standard Java application is occupied by garbage collection. Furthermore, applications including frequent repetition of allocation (reserving) and freeing (deallocation) of memory, of which generation of objects inside a loop is a representative example, devote a large proportion of execution time to garbage collection. This reduces the amount of time available for executing the application itself. Thus, even if optimizing program code has speeded up its execution, the effect of such improvements will be limited.
A further disadvantage of garbage collection is that it is impossible to estimate how long it will take to perform until it has been completed. This means that the risk of suspension of program execution or a dramatic drop in performance during garbage collection can never be entirely dismissed. This kind of risk may prove to be a fatal flaw when writing applications that demand an interactive processing thread and real-time implementation.
Since the dynamic memory management performed by Java execution threads includes garbage collection, as described above, Java is said to be unsuitable for writing programs which demand real-time implementation. However, it may be possible to overcome such problems by reducing some of the load placed on the execution thread by dynamic memory management (in other words by using some kind of mechanism to change the Java bytecode when compiling from source code into Java bytecode).
The following techniques disclosed in Japanese Laid-Open Patent 8-272621 and Japanese Laid-Open Patent 9-330232 both use a compiler to assist in dynamic memory management.
Japanese Laid-Open Patent 8-272621 discloses a technique for analyzing memory lifetimes, in which the malloc and free functions used in a source program for dynamically allocating and freeing memory in the heap area are changed to an alloca function for allocating and freeing dynamic memory inside a function stack at a higher processing speed.
Japanese Laid-Open Patent 9-330232 discloses a technique for analyzing lifetimes in a dynamically allocated memory, and changing the source program so that memory areas with lifetimes which do not overlap are grouped together, and memory in each group is shared. This reduces the need to call library functions for dynamically allocating and freeing memory.
However, both of these techniques share the following weaknesses:
(1) Since a lifetime of an allocated memory area is assumed to continue until a free instruction is issued by the program, lifetimes are still likely to be unnecessarily prolonged.
(2) The above change of functions cannot be applied if a free instruction is omitted from the program due to a programmer error (when manual memory management is used by a programming language such as C++) or if the programming language is not equipped for indicating memory freeing explicitly in the program (when automatic memory management is used by a programming language such as Java). As a result, there cannot be said to be sufficient reduction in the amount of dynamic storage management performed by the execution thread.
In view of the above problems, the object of the present invention is to provide a program conversion apparatus capable of reducing the amount of dynamic storage management placed on the execution thread when a program is executed.
A first program conversion apparatus relating to the invention converts a source program to an executable program, the source program including a first descriptor indicating dynamic memory allocation.
This program conversion apparatus includes a specifying unit for specifying in the source program a reference descriptor that is last to be executed from reference descriptors indicating references to memory allocated by the first descriptor; and a generating unit for generating an instruction for freeing the allocated memory at a position in the executable program immediately following an instruction that corresponds to the specified reference descriptor.
When an executable program written in Java or a similar programming language is executed, this construction prevents memory lifetimes from being unnecessarily prolonged, thereby reducing the amount of dynamic memory management performed by the execution thread.
A second program conversion apparatus relating to the invention converts a source program to an executable program, the source program including a first descriptor indicating dynamic memory allocation, and a second descriptor indicating memory allocation only when instructions are executed within a specified block.
This program conversion apparatus includes a specifying unit for specifying a lifetime of allocated memory by referring to positions in the source program of (1) the first descriptor and (2) reference descriptors indicating references to memory allocated by the first descriptor; a determining unit for determining whether the specified lifetime is confined within the specified block; and a generating unit for generating an instruction in an executable program when the specified lifetime is determined to be confined within the specified block, so that memory indicated as being allocated by the first descriptor in the source program is indicated as being allocated by the second descriptor.
When an executable program written in Java or a similar programming language is executed, this construction prevents memory lifetimes from being unnecessarily prolonged, thereby reducing the amount of dynamic memory management performed by the execution thread.
A third program conversion apparatus relating to the invention converts a source program to an executable program, the source program including a first descriptor indicating dynamic memory allocation for a specified object, a second descriptor indicating (1) repetition of instructions within a specified block and (2) a number of repetitions, and a third descriptor indicating continuous dynamic memory allocation for a specified plurality of objects.
This program conversion apparatus includes a specifying unit for specifying a position of the first descriptor in a source program; a determining unit for determining whether the specified position of the first descriptor is within the specified block; a detecting unit for detecting the number of repetitions shown by the second descriptor corresponding to the specified block; and a generating unit for generating an instruction in an executable program when the specified position of the first descriptor is determined to be within the specified block, so that memory, determined by repeating the memory allocation indicated by the first descriptor for the number of repetitions shown by the second descriptor, is indicated as being allocated by the third descriptor, the third descriptor being positioned outside the specified block.
When an executable program written in a programming language such as Java, C or C++ is executed, this construction prevents dynamic memory from being allocated each time a program block is repeated, thereby reducing the amount of dynamic memory management performed by the execution thread. Furthermore, the memory for each block repetition is allocated continuously, enabling the recycling performed in dynamic memory management to be performed effectively.
A fourth program conversion apparatus relating to the invention converts a source program to an executable program, the source program including a first descriptor indicating dynamic memory allocation for a specified object, a second descriptor indicating (1) repetition of instructions within a specified small block, and (2) a number of repetitions, and a third descriptor indicating continuous memory allocation for a specified plurality of objects only when instructions are executed within a specified large block that includes the specified small block.
This program conversion apparatus includes a specifying unit for specifying a lifetime of allocated memory, by referring to positions in the source program of (i) the first descriptor and (ii) reference descriptors indicating references to memory allocated by the first descriptor; a determining unit for determining whether the specified lifetime is confined within the specified large block and also whether the position of the first descriptor is within the specified small block; a detecting unit for detecting the number of repetitions shown by the second descriptor corresponding to the specified small block; and a generating unit for generating an instruction in the executable program when (a) the specified lifetime is determined to be confined within the specified large block and (b) the position of the first descriptor is determined to be within the specified small block, so that memory, determined by repeating the memory allocation indicated by the first descriptor for the number of repetitions shown by the second descriptor, is indicated as being allocated by the third descriptor, the third descriptor being positioned within the specified large block but outside the specified small block.
When an executable program written in Java or a similar programming language is executed, this construction prevents unnecessary dynamic memory allocation, thereby reducing the amount of dynamic memory management performed by the execution thread.
A fifth program conversion apparatus relating to the invention converts a source program to an executable program, the source program including a first descriptor indicating dynamic memory allocation, a second descriptor indicating repetition of instructions within a specified small block, and a third descriptor indicating memory allocation only when instructions are executed within a specified large block that includes the specified small block.
The program conversion apparatus includes a specifying unit for specifying a lifetime of allocated memory, by referring to positions in the source program of (1) the first descriptor and (2) reference descriptors indicating references to memory allocated by the first descriptor; a determining unit for determining whether the specified lifetime lasts for one execution duration of the specified small block; and a generating unit for generating an instruction for the executable program when the specified lifetime is determined to last for less than one execution duration of the specified small block, so that memory indicated as being allocated by the first descriptor in the source program is indicated as being allocated by the third descriptor, the third descriptor being positioned within the specified large block but outside the specified small block.
When an executable program written in Java or a similar programming language is executed, this construction prevents unnecessary dynamic memory allocation, thereby reducing the amount of dynamic memory management performed by the execution thread.